package com.du.algorithm.primary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Desc :
 * @Author: shuangdu
 * @date : 2023/10/11
 */
public class DfsExample {
    static class TreeNode {
        int val;
        TreeNode pre;
        TreeNode next;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        // 构建树结构
        TreeNode root = new TreeNode(-1);
        root.pre = null;
        root.next = new TreeNode(100);
        root.next.pre = root;
        root.next.next = new TreeNode(101);
        root.next.next.pre = root.next;
        root.next.next.next = new TreeNode(102);

        // 搜索条件
        int target = 101;

        // 调用DFS函数进行搜索
        TreeNode result = dfs(root, target);
        if (result != null) {
            System.out.println("找到满足条件的子树");
        } else {
            System.out.println("未找到满足条件的子树");
        }
    }

    public static TreeNode dfs(TreeNode node, int target) {
        if (node == null) {
            return null;
        }

        if (node.val == target) {
            return node;
        }

        TreeNode nextResult = dfs(node.next, target);
        if (nextResult != null) {
            return nextResult;
        }

        return null;
    }
}
